In many conventional memory systems, such as random access memory, binary digits (bits) are stored in memory cells, and are accessed by a processor that specifies a linear address that is associated with the given cell. This system provides rapid access to any portion of the memory system within certain limitations. To facilitate processor control, each operation that accesses memory must declare, as a part of the instruction, the address of the memory cell/cells required. Standard memory systems are not well designed for a content based search. Content based searches in standard memory require software based algorithmic search under the control of the microprocessor. Many memory operations are required to perform a search. These searches are neither quick nor efficient in using processor resources.
To overcome these inadequacies an associative memory system called Content Addressable Memory (CAM) has been developed. CAM allows cells to be referenced by their contents, so it has first found use in lookup table implementations such as cache memory subsystems and is now rapidly finding use in networking systems. CAM's most valuable feature is its ability to perform a search and compare of multiple locations as a single operation, in which search data is compared with data stored within the CAM. Typically search data is loaded onto search lines and compared with stored words in the CAM. During a search-and-compare operation, a match or mismatch signal associated with each stored word is generated on a matchline, indicating whether the search word matches a stored word or not.
A typical CAM block diagram is shown in FIG. 1. The CAM 10 includes a matrix, or array 100, of CAM cells (not shown) arranged in rows and columns. For a ternary CAM, the cells are typically either DRAM or SRAM type, and store one of three states: logic “1”, logic “0” and “don't care”, as two bits of data. An array of DRAM based ternary CAM cells, as described in Canadian Patent Application No. 2,266,062, filed Mar. 31, 1999, the contents of which are incorporated herein by reference, have the advantage of occupying significantly less silicon area than their SRAM based counterparts. The description of the operation of the ternary DRAM cell is detailed in the aforementioned reference. A predetermined number of CAM cells in a row store a word of data. An address decoder 12 is used to select any row within the CAM array 100 to allow data to be written into or read out of the selected row. Although most commonly, data is written or loaded into the CAM and searched. Data access circuitry such as bitlines and column selection devices, are located within the array 100 to transfer data into and out of the array 100. Located within CAM array 100 for each row of CAM cells are matchline sense circuits (not shown) used for search-and-compare operations. The various registers 15 receive and hold data from the data I/O block 20 for search-and-compare operations, and other components of the CAM include the control circuit block 14, the flag logic block 16, the voltage supply generation block 18, various control and address registers 22, refresh counter 28 and JTAG block 24.
The matchline sense circuits are used during search-and-compare operations for outputting a result indicating a successful or unsuccessful match of a search word against the stored word in the row. The results for all rows are processed by the priority encoder 200 to output the address (Match Address) corresponding to the location of a matched word. The match address is stored in match address registers 25 before being output by the match address output block 26. The generation of the match address is relatively simple when there is only one stored word which matches the search word. However, when there are many stored words matching the search word, the priority encoder is still limited to provide only one match address. Hence, a rule is applied in which only the highest priority matching word is accepted, and all lesser priority matching words are ignored. Within the context of CAM's, the highest priority matching word is located at the lowest physical address in the CAM array and accordingly, the lowest priority matching word is located at the highest physical address in the CAM array. For example, if two words located at binary address 0001 and 1001 match the search word, the word stored at binary address 0001 would have the highest priority. In general, the priority encoder 200 of the CAM is responsible for determining the highest priority matching word among many matching words, and generating the address corresponding to the highest priority matching word.
A more detailed block diagram of a typical priority encoder 200 is shown in FIG. 2. The priority encoder includes a multiple match resolver block 204 and a ROM address decoder block 206 for generating an 8-bit address. Multiplexors 202 receive matchline sense output signals ML_OUT0 to ML_OUT255 from the matchline sense circuits, and an empty data signal EMPTY0 to EMPTY255. A common control signal SELECT EMPTY connected to each multiplexor 202 selects empty data for input to the multiple match resolver block 204 when active. However, for the purposes of the following discussion, it is assumed that SELECT EMPTY is inactive, and only the matchline sense output signals are passed to the multiple match resolver block 204. For each input of the multiple match resolver block 204, there is exactly one corresponding output 208 supplied to ROM decoder block 206. In general operation, when multiple match resolver block 204 receives one or more active ML_OUT signals, ic. when a match between the stored word in the CAM and search word occurs, multiple match resolver block 204 determines which stored word has the highest priority and activates the corresponding output signal 208. ROM block 206 then generates an 8-bit address corresponding to the active output signal 208. Although the input signals are arranged in sequential order, it is the logical order assigned to the physical connection of the signal within multiple match resolver block 204 which is significant. In other words, if it is understood that ML_OUT0 is the highest priority location and ML_OUT255 is the lowest priority location, then the ML_OUT inputs could be connected in any order as long as the internal connections within multiple match resolver block 204 are correspondingly assigned according to their logical priority.
A disadvantage with the scheme shown in FIG. 2 is the long duration of time required to produce the match address after the matchline sense output signals are presented to the multiple match resolver block 204. The delay in receiving the match address is approximately 12 ns, a significant amount of time which delays subsequent CAM operations. Most of this delay is contributed by the memory access operation of the ROM.
It is therefore desirable to provide a searchline control circuit capable of operating at high speed to improve CAM performance.